1. Field of the Invention
The present invention relates generally to processing image and video data. More particularly, the present invention relates to partitioning an area of an image or video frame into sub-areas.
2. Description of the Background Art
In image and video processing, it is often desirable to divide an area of an image into sub-areas to facilitate processing. For example, for discrete cosine transform (DCT) processing, an image is typically divided into blocks, and DCT is applied to those blocks. When more specific shape information regarding regions within an image is available, then it makes sense to take advantage of the shape information, for example, for coding efficiency, improved filtering, matching, and so on. However, sometimes such regions may be too large or awkwardly shaped to process efficiently. Dividing such large or awkwardly shaped regions into sub-regions that reflect some of the geometric information available regarding the region would be highly desirable.
One example where such large or awkwardly shaped regions often arises is segment-based motion compensation where exposed areas are created. For example, as an object or segment moves from frame to frame, previously hidden areas become exposed. These exposed areas are typically arbitrarily-shaped and non-uniform. Hence, encoding exposed areas is problematic and typically rather inefficient. A solution dealing with exposed areas may also have wider applicability to other similar or related tasks in image processing.
In accordance with one embodiment of the invention, a processing method and apparatus is provided for partitioning areas of an image. The partitioning creates sub-areas in shapes and sizes that may be effectively dealt with and efficiently compressed. The partitioning advantageously divides an arbitrarily shaped area by xe2x80x9cpinching,xe2x80x9d xe2x80x9cslicing,xe2x80x9d and/or xe2x80x9ccleavingxe2x80x9d the area into manageable sub-areas to facilitate further processing. Such pinching, slicing, and/or cleaving may be applied to the area in any order.
In accordance with another embodiment of the invention, a processing method and apparatus is provided for partitioning a bounded area into sub-areas by determining pinch cuts located in narrow regions near rapid changes in area width, and dividing the area into sub-areas separated by the pinch cuts. The pinch cuts advantageously facilitate further processing by separating either a narrow region from a wide region or two wide regions from each other.
In accordance with another embodiment of the invention, a processing method and apparatus is provided for placing slice cuts to partition a bounded two-dimensional area. The method and apparatus determines a medial axis comprising at least one medial line segment approximately midway between two boundary line segments, and places the slices approximately perpendicular to the medial line segment and spaced approximately evenly along the medial line segment. The slice cuts advantageously divide elongated areas into sub-areas that are typically more efficient to further process.
In accordance with another embodiment of the invention, a method and apparatus is provided for processing points in a bounded area to locate a medial axis. The method and apparatus determines a nearest boundary point outside the area corresponding to each point inside the area, finds adjacent points inside the area which have different corresponding nearest boundary points separated by at least a threshold arc length, generates paths between said adjacent points with different corresponding nearest boundary points, and locates the medial axis from amongst said paths. Locating a medial axis advantageously facilitates determination of the pinch and slice cuts for partitioning arbitrarily-shaped areas.
In accordance with another embodiment of the invention, an electronically-implemented method and apparatus is provided for processing a bounded two-dimensional area in an array of points to determine, for each point inside the area, a nearest boundary point outside the area as measured by Euclidean distances. This technique based on Euclidean distances may be considered to be superior to prior techniques based on Manhattan distances. The Euclidean distances advantageously facilitate locating the medial axis.